1. Field of the Invention
The present invention relates to the field of error detecting and correcting codes for computer systems.
2. Prior Art
Digital computer systems work with binary coded information wherein data is represented in the computer system as a series of pieces of information, each piece being stored as either a relatively high or relatively low electrical state. Typically, the high state is represented by a 1 and the low state is represented by a 0. Computer systems are subject to a variety of problems which may cause an electrically high state to be altered to an electrically low state or an electrically low state may be altered to an electrically high state It is important to be able to detect such errors and advantageous to be able to correct such errors. In any error checking and correcting scheme there are at least two conflicting priorities. First, the scheme must be as simple and compact as possible so as not to unduly add complexity to the system or decrease its speed. Second, the scheme should be capable of correcting as many errors as possible and detecting all expected errors
Numerous examples of error checking and correcting schemes are known One of the simplest examples is the use of parity bits to detect single bit errors in a stream of data. The use of a single parity bit will detect single bit errors but is not capable of correcting single bit errors and will not detect 2-bit errors.
In 1950 Richard Hamming developed a method for detecting and correcting single bit errors. This method is known as a Hamming Code. An example of a binary coded piece of information coded using the Hamming Code method is illustrated in FIG. 2.
Another coding method is known as Product Codes. This method has numerous variations. One variation is illustrated in FIGS. 3a and 3b and utilizes an overall parity check on each row and each column in a block of data. This method is capable of detecting and correcting all single bit errors. Essentially this method amounts to computing parity bits based on a set of data and then generating a second set of parity bits based on the first set of parity bits.